Subject: Re: Algorithm for finding all possible combinations
From: [email-masked] (Mike Gleason)
Date: 30 Jan 1994 22:57:43 GMT
Newsgroups: comp.programming

[email-masked] (Remo Williams) writes:

|>	I have three chunks of a data, named a, b and c. I need to
|>	process them in every possible order. So I need to organize
|>	them like this:
|>		a b c
|>		a c b
|>		b a c
|>		b c a
|>		c a b
|>		c b a

|Pseduocode:	z:=c
|		for x:= a to c do
|		    for y:= b to c do
|			if (x<y) and (y<z) do
|			write (x,y,z)
|			write (z,y,z)

That's swell, but I believe the original poster wanted something for
the general case.

Here's a chunk of code I wrote last year for this purpose.  This is
copyrighted code, but I don't mind what you use it for as long as
you don't use it as your homework assignment:

/* WeakPermDriver.c
 * Copyright 1993 by Mike Gleason.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DONE				(1)
#define NOT_DONE			(0)
#define DEFAULT_N			(4)
#define MAXPERMSIZE			(32)

typedef int SetElement;
typedef SetElement Permutation[MAXPERMSIZE];

static void PermToCycle(Permutation p, int permSize, char *cycle)
{
	int i, j;
	Permutation used;
	SetElement x, y, cstart;
	int ncycles = 0;

	for (i=0; i<permSize; i++)
		used[i] = 0;

	*cycle++ = '(';
	x = 1;
	used[x-1] = 1;
	cstart = x;
	*cycle++ = (char)(x + '0');

	for (;;) {
		y = p[x-1];
		if (y == cstart) {
			/* End cycle. */
			/* First get rid of any 1-cycles. */
			if (cycle[-2] == '(')
				cycle -= 2;
			else {
				*cycle++ = ')';
				++ncycles;	/* Count 2-cycles, and larger. */
			}
			x = -1;
			for (j=0; j<permSize; j++)
				if (used[j] == 0) {
					x = j + 1;
					cstart = x;
					used[j] = 1;
					*cycle++ = '(';
					*cycle++ = (char)(x + '0');
					break;
				}
			if (x < 0)
				break;		
		} else {
			*cycle++ = (char)(y + '0');
			used[y - 1] = 1;
			x = y;
		}
	}
	if (ncycles == 0)
		*cycle++ = '1';		/* Must be identity cycles. */
	*cycle = 0;
}	/* PermToCycle */

static void PrintPerm(Permutation p, int permSize, int permNum)
{
	int i;
	char cy[128];

	printf("%3d: ", permNum);
	PermToCycle(p, permSize, cy);
	for (i=0; i<permSize; i++)
		printf("%d%c", p[i], (i == permSize - 1) ? ' ' : '-');
	printf(" = %s\n", cy);
}	/* PrintPerm */

static int NextPerm(Permutation p, int permSize)
{
	int i;
	
	/* First find where in the permutation the "largest" element is. */
	for (i=0; p[i] != permSize; ) ++i;

	/* Check to see if that element is in the first position. */
	if (i==0) {
		/* If this element is in the first position, and the size of
		 * the (sub)permutation is only 1 element, there is no next
		 * permutation, so say we're finished.  We'll get to this point
		 * if the permutation we were asked to "next" was in descending
		 * order, and that one is the last one, therefore there is no
		 * next permutation.
		 */
		if (permSize==1)
			return DONE;

		/* Otherwise, shift all the other elements "back" one slot. */
		memmove(p, p+1, (permSize - 1) * sizeof(SetElement));
		
		/* Recursively call myself to work on a smaller sub-permutation. */
		if (NextPerm(p, permSize - 1) == DONE)
			return DONE;
			
		/* Now stick the "largest" element in the last position. */
		p[permSize - 1] = (SetElement) permSize;
	} else {
		p[i] = p[i-1];
		p[i-1] = permSize;
	}
	return (NOT_DONE);
}	/* NextPerm */

void main(int argc, char *argv[])
{
	int n = DEFAULT_N;	/* Number of elements in the set to permute. */
	int permNum = 0;	/* Not the rank, since they're not computed
						 * in ascending order.
						 */
	Permutation perm;	/* The set of elements. */
	int i;

	/* Get the 'n' from the command line, if you specified one. */
	if (argc > 1) {
		i = atoi(argv[1]);
		if ((i > 1) && (i <= MAXPERMSIZE))
			n = i;
	}

	/* Initialize the first permutation. */
	for (i=0; i<n; i++)
		perm[i] = i+1;
	
	/* Loop until we've found them all. */
	do {
		PrintPerm(perm, n, ++permNum);
	} while (NextPerm(perm, n) == NOT_DONE);
	
	exit(0);
}	/* main */

/* eof */
--
______________________________________________________________________________
mike gleason                 [email-masked]             NCEMRSoft, baby!